Radio waves propagate at the speed of light. In cellular radio transmissions, a transmitted signal can arrive at a receiver at multiple times due to refraction, diffraction or reflection. Refraction occurs when the path of propagation of the transmitted signal bends to follow the curvature of the earth. Diffraction occurs when the path of propagation passes around obstacles. Reflection occurs when a transmitted signal bounces off of either the atmosphere, or obstacles in the path of propagation such as terrain, water tanks or buildings. Each of these phenomena can contribute to a multiplicity of signals being received at the receiver. Each of these signals was initially the originally transmitted signal. Each of the received signals is uniquely distorted by the particular path it transverses. Each signal is received at slightly different times due to the differences in the length of the path of propagation. If the transmitter is mobile, such as a mobile cellular telephone, the received signals vary. When the transmitted signal is digital symbols, intersymbol interference occurs and may extend over several symbol time periods. The receiver must reliably extract the transmitted signal from these various received signals.
Time division multiple access encoded information is transmitted in multiple channels per carrier. In accordance with the Group Special Mobile (GSM) standard, there are eight channels per carrier. Each channel is provided a time slot of one-half millisecond. Each time slot provides a frame of bits, sometimes called a transmission burst, during transmission. A portion of the bits in each frame are set aside as a training segment for system use. The bits of the training segment, or a portion of them, have been used as a means to adapt the decoding process to compensate for channel characteristics. However, these bits are received only once during each frame whereas the channel characteristics can change over the entire time during which the frame is transmitted, such that the channel characteristics during the training segment are not representative of the channel characteristics of the entire frame.
A Viterbi decoder is a maximum likelihood decoder that provides forward error correction. Viterbi decoding is used in decoding a sequence of encoded symbols, such as a bit stream. The bit stream can represent encoded information in telecommunication system transmission through various media with each set of bits representing a symbol instant. In the decoding process, the Viterbi decoder works back through a sequence of possible bit sequences at each symbol instant to determine which one bit sequence, is most likely to have been transmitted. The possible transitions from a bit at one symbol instant, or state, to a bit at a next, subsequent, symbol instant or state is limited. Each possible transition from one state to a next state can be shown graphically and is defined as a branch. A sequence of interconnected branches is defined as a path. Each state can only transition to a limited number of next states upon receipt of the next bit in the bit stream. Thus, some paths survive and other paths do not survive during the decoding process. By eliminating those transitions that are not permissible, computational efficiency can be achieved in determining the most likely paths to survive. The Viterbi decoder typically defines and calculates a branch metric associated with each branch and employs this branch metric to determine which paths survive and which paths do not survive.
A branch metric is calculated at each symbol instant for each possible branch. Each path has an associated metric, accumulated cost, that is updated at each symbol instant. For each possible transition, the accumulated cost for the next state is calculated as the lesser of the sum of the branch metric for the possible transitions and the path accumulated cost at the previous state.
While several paths survive the transition from one symbol instant to the next symbol instant, there is only one minimum accumulated cost path from the least of the minimum accumulated costs at a symbol instant, back through the possible branches. Representing the sequential symbol instants in an array is referred to as a trellis. Identifying the minimum accumulated cost path starting with a given symbol instant it referred to as a traceback. The number of symbol instants back through the trellis that the minimum accumulated cost path extends is the length, or depth, of the traceback. The individual state in the trellis associated with the minimum accumulated cost at the end of the traceback is translated into the most likely bit to have been transmitted in that symbol instant. This bit is referred to as a decoded symbol.
Historically, Viterbi decoders have used a fixed length traceback to decode encoded symbols. The longer the traceback length, the greater the accuracy in determining a decoded symbol. When using modulo addressing, the trellis appears to be circular. Initial long tracebacks cycle into portions of the trellis having surviving branch data from a previous transmission burst that has not yet been overwritten. A need remains in the art for a technique to initially provide short length tracebacks in a Viterbi decoder to minimize tracebacks from cycling into branch origin data from a previous transmission burst that has not yet been over-written.